Hash tables are generally used for providing a unique mapping between a set of input values, referred to as key values, and storage locations for corresponding output values, referred to as buckets. Hash tables are used in various contexts, such as, for example, database applications, implementing data structures such as associative arrays and sets, memory caches, networking applications, or other situations in which a unique mapping between input values and output values is desirable.
One technique for increasing the speed of hash tables is to provide a hardware-based hash table. When a hash table is implemented in hardware, the hash table draws power that may otherwise be budgeted to other hardware features of a hardware unit including the hash table. The amount of power consumed by the hardware-based hash table is approximately proportional to the silicon area covered by the hash table. Likewise, the amount of keys and buckets supported by the hardware-based hash table is also approximately proportional to the silicon area covered by the hash table. Thus, to support a large number of keys and buckets, a larger area of silicon must be devoted to the hash table, requiring a larger amount of power for the hash table. In many cases, hardware-based hash tables are implemented such that they support as large a set of values as possible to allow use in a wide range of applications, requiring a trade-off of chip area and power consumption for increased capacity.